package 链表;

/**
 * @author admin
 * @version 1.0.0
 * @ClassName 删除排序链表中的重复元素二.java
 * @Description TODO
 * @createTime 2020年11月21日 09:01:00
 */
public class 删除排序链表中的重复元素二 {
    public class ListNode {
      int val;
      ListNode next;
      ListNode(int x) { val = x; }
  }

  /*
  * 了方便处理头结点，这里我们添加一个哨兵节点no1，让他指向head！（实不相瞒是看大佬题解学到的超级有用！！）
（所有链表题加一个哨兵节点都可以非常方便处理头部节点！）

然后就用一前一后的p1,p2指针来查看是否有相同的节点，这里我分两种情况
如果有相同的节点：（r=1)
就让p2后移直到一个新节点
直接用p1.next=p2.next 就可以删掉所有重复节点啦！！
如果没有相同的节点：(r=0)
就是寻常的p1,p2后移即可
*/
    class Solution {
        public ListNode deleteDuplicates(ListNode head) {
            ListNode no1=new ListNode(0);no1.next=head;
            ListNode p1=no1,p2=head;
            int r=0;
            while(p1.next!=null){
                while(p2.next!=null&&p2.next.val==p1.next.val){
                    p2=p2.next;
                    r=1;//如果有重复节点则r置为1
                }
                if(r==1){
                    p1.next=p2.next;//删掉重复节点
                    p2=p2.next;//再指针后移！！这时候p1不用动！
                    r=0;
                }else{
                    p1=p2;//指针后移!p1,p2都向后移动一下
                    if(p2.next!=null)
                    {
                        p2=p2.next;
                    }
                }
            }
            return no1.next;
        }
    }

   /**
    * 思路：删除所有头部的重复节点，返回不重复的第一个节点。
    *
    *     1.特殊情况，头节点为null或头节点下一节点为null，直接返回头节点，这时不存在重复节点
    *     2.如果头节点与，头节点的下一节点值相等，跳过所有相等节点。递归调用函数判断最后一个跳过节点的后一节点。
    *     3.如果头节点与，头节点的下一节点值不等，递归调用函数判断头节点的后一节点。
    *
    *
    * */
    class Solution2 {
        public ListNode deleteDuplicates(ListNode head) {
            if (head == null || head.next == null) {
                return head;
            }
            if (head.val == head.next.val) {
                while (head != null && head.next != null && head.val == head.next.val) {
                    head = head.next;
                }
                return deleteDuplicates(head.next);
            } else {
                head.next = deleteDuplicates(head.next);
                return head;
            }
        }
    }


}
